package Queue;

// 定义节点类
@SuppressWarnings("all")
class Node<T>{
    T val; // 节点的值域
    Node<T> next = null; // 节点的指针域,初始化为空
    int prority; // 节点的优先级 数值越大，优先级越高

    public Node(){}; // 无参构造
    public Node(T val,int prority) { // 有参构造
        this.val = val;
        this.prority = prority;
    }
    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                ", next=" + next +
                ", prority=" + prority +
                '}';
    }
}
// 定义一个优先队列的数据结构
/**
 * 下面定义的优先队列的结构：返回优先级最高的节点，删除优先级最高的节点的时间复杂度为O(1)
 * 但是插入操作的时间复杂度为O(n),如果频繁的进行插入操作，总体的时间效率会比较低，所以我们
 * 需要对下面给出的结构进行一定的优化，我们优化的方式就是通过heap这种数据结构，将时间复杂度
 * 降低到O(logn)
 * @param <T>
 */
@SuppressWarnings("all")
public class PriorityQueue<T> {
    private int maxSize = 5; // 默认的最大长度
    private Node<T> QueueHead = null; // 初始化一个空的队头元素

    // 判断当前队列是否为空
    public boolean isEmpty() {
        return this.QueueHead == null;
    }

    // 返回当前队列的实际长度
    public int size() {
        if (this.isEmpty()) {
            return 0;
        }
        int queueSize = 0;
        Node<T> cur = QueueHead;
        while (cur != null) {
            queueSize++;
        }
        return queueSize;
    }

    // 判断当前队列是否满
    public boolean isFull() {
        return this.size() == this.maxSize;
    }

    // 扩容
    public void resize(int maxSize,Node<T> queueHead) {
        Node<T> newQueueHead = null;
        Node<T> curOld = queueHead; // 定义指针，遍历queueHead
        Node<T> curNew = null; // 遍历新队列
        while (curOld != null) {
            if (newQueueHead == null) {
                // 当新队列为空的时候，curNew也是null，此时还没有next指针
                newQueueHead = curOld;
                curNew = newQueueHead; // 在将curNew接到新队列的头节点处
                curOld = curOld.next;
            } else {
                // 当前新队列不空
                curNew.next = curOld;
                curOld = curOld.next;
            }
        }
        QueueHead = newQueueHead;
        this.maxSize = 2 * maxSize;
    }

    // 添加节点到队列中，保持优先级的顺序 优先级高的节点在前面
    public void add(T val,int priority) {
        if (isEmpty()) {
            // 如果当前队列为空
            QueueHead = new Node<>(val,priority); // 将当前节点置为队列的头节点
            return;
        }
        // 判断当前队列是否满
        if (isFull()) {
            // 如果当前队列为满的，先进行扩容 ，默认为原来的两倍 2 * maxSize
            this.resize(maxSize,this.QueueHead);
        }
        // 创建新节点
        Node<T> newNode = new Node<>(val,priority);
        // 创建遍历指针
        Node<T> cur = QueueHead;
        // 我们的目的就是找到这样一个节点：cur指向的节点的优先级大等于节点，cur后边的节点的优先级小于等于新节点
        while (cur.next != null) { // 遍历到倒数第二个节点，因为为节点没后继节点
            if (cur.prority >= newNode.prority && cur.next.prority <= newNode.prority) {
                newNode.next = cur.next;
                cur.next = newNode;
                break;
            }
        }
        //  最后一个节点
        cur.next = newNode;
    }

    // 查看队列优先级最高的节点  即头节点
    public Node<T> peek() {
        return QueueHead;
    }

    // 删除优先级最高的节点 即头节点
    public Node<T> poll() {
        if (this.isEmpty()) {
            return null;
        }
        Node<T> head = QueueHead;
        QueueHead = QueueHead.next;
        return head;
    }
}
